package ac

import (
	"sync"
)

// Node AC自动机节点结构
type Node struct {
	Children map[rune]*Node // 子节点
	Fail     *Node          // 失败指针
	Depth    int            // 节点深度
	End      bool           // 是否为单词结尾
	Word     string         // 如果是单词结尾，存储完整单词
}

// Automaton AC自动机结构
type Automaton struct {
	root *Node
	mux  sync.RWMutex
}

// NewAutomaton 创建新的AC自动机
func NewAutomaton() *Automaton {
	return &Automaton{
		root: &Node{
			Children: make(map[rune]*Node),
			Depth:    0,
		},
	}
}

// Insert 插入敏感词
func (ac *Automaton) Insert(word string) {
	ac.mux.Lock()
	defer ac.mux.Unlock()

	node := ac.root
	for _, char := range word {
		if node.Children == nil {
			node.Children = make(map[rune]*Node)
		}
		if _, exists := node.Children[char]; !exists {
			node.Children[char] = &Node{
				Children: make(map[rune]*Node),
				Depth:    node.Depth + 1,
			}
		}
		node = node.Children[char]
	}
	node.End = true
	node.Word = word
}

// BuildFailureLinks 构建失败指针
func (ac *Automaton) BuildFailureLinks() {
	ac.mux.Lock()
	defer ac.mux.Unlock()

	// 使用BFS构建失败指针
	queue := make([]*Node, 0)

	// 根节点的子节点失败指针指向根
	for _, child := range ac.root.Children {
		child.Fail = ac.root
		queue = append(queue, child)
	}

	// BFS处理其他节点
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		for char, child := range node.Children {
			queue = append(queue, child)

			// 从父节点的失败指针开始查找
			failNode := node.Fail
			for failNode != nil {
				if next, exists := failNode.Children[char]; exists {
					child.Fail = next
					break
				}
				failNode = failNode.Fail
			}

			// 如果没找到匹配的失败指针，指向根节点
			if failNode == nil {
				child.Fail = ac.root
			}
		}
	}
}

// Search 查找文本中的敏感词
func (ac *Automaton) Search(text string) []string {
	ac.mux.RLock()
	defer ac.mux.RUnlock()

	result := make([]string, 0)
	node := ac.root

	// 遍历文本
	for _, char := range text {
		// 查找匹配的节点
		for node != ac.root && node.Children[char] == nil {
			node = node.Fail
		}

		// 如果找到匹配的子节点，移动到子节点
		if next, exists := node.Children[char]; exists {
			node = next
		}

		// 检查当前节点是否是某个敏感词的结尾
		for current := node; current != ac.root; current = current.Fail {
			if current.End {
				result = append(result, current.Word)
			}
		}
	}

	return result
}

// Clear 清空AC自动机
func (ac *Automaton) Clear() {
	ac.mux.Lock()
	defer ac.mux.Unlock()

	ac.root = &Node{
		Children: make(map[rune]*Node),
		Depth:    0,
	}
}
